1. Field of the Invention
This invention relates to image signal processing apparatus and methods.
2. Description of the Prior Art
It is known to manipulate an image signal in the spatial domain by mapping words of the signal to produce a mapped image which is manipulated by virtue of the mapping process in a manner dictated by the mapping function that is employed in carrying out the process. Such a technique may, for example, be employed in the creation of digital video effects. The mapping process may involve compression and/or rotation of the image. Moreover, the extent of compression and/or rotation may vary from area to area of the mapped (manipulated) image. As is explained in more detail below, both compression and rotation may lead to aliasing, which (in the absence of preventive measures) will cause degradation of the image.
In more detail, FIG. 1 of the accompanying drawings shows, in outline, an image processing apparatus that can be used, for example in the creation of digital video effects, to map an image signal into a memory in accordance with a desired mapping function in order to manipulate or transform the image into a desired form. An input image or picture signal is applied to an input port or terminal 10 of a memory shown schematically at 12. The input image signal comprises a sequence of digital words (for example 8-bit words) which may comprise digitized samples (sampling frequency [rate] fs) of, for example, a raster scan video signal obtained, for instance, from a television camera. The respective input words or samples are stored in respective locations of the memory 12, which may for example be a field store or a frame store in the case of a video signal, in accordance with addresses allocated to the respective samples by an address generator 14. The address generator 14 generates addresses at the frequency fs in accordance with a mapping function so as to map the samples into the memory 12 in such a manner that, when the contents of the memory are read out to produce an output image signal at the frequency fs on an output port or terminal 16, the output picture or image represented by the output image signal will have been manipulated in appearance, as compared to the input picture or image, in a manner determined by the mapping function, so as to achieve a desired visual effect.
The operation of the arrangement of FIG. 1 will now be described in more detail, considering first a case in which the addresses generated by the address generator 14 are such that no image manipulation is achieved. The address allocated to each sample of the input signal comprises information in coded-bit form which represents or points to the x and y coordinates of a memory location in an x, y coordinate system of which the upper left hand corner of the memory 12 as represented in FIG. 1 can be considered to constitute the origin. Thus, the first sample of the input image signal, which is the first sample of a first line of the image, is allocated an address pointing to a memory location (0, 1), that is a memory location having the address coordinates: x=0, y=1. Successive samples of the first line are allocated addresses corresponding to the memory locations (0,2), (0,3) . . . (0,n), where n is the number of samples per line. The samples of successive lines are allocated addresses (1,1) to (1,n), (2,1) to (2,n) and so forth, up to (m,1) to (m,n) for the last line, where m is the number of lines in the image. At this point, the whole image (for example one field or frame of a video signal) has been stored. The stored image then is read out by outputting the contents of the memory locations in the order (0,1) to (0,n), (1,1) to (1,n) . . . (m,1) to (m,n). As will be apparent, the output image represented by the output image signal is in this case an unmanipulated representation of the input image.
It should, of course, be appreciated that the relative dispositions of the respective memory locations in FIG. 1 are shown schematically and that they need not in practice be relatively disposed in the manner shown in FIG. 1.
A description will now be given, with reference to FIG. 2 of the accompanying drawings, of a case in which the input image is manipulated. In this case, the input image is to be manipulated so that the output image will appear within an area 18 shown in FIG. 2. The area 18, which has been selected arbitrarily to illustrate by way of example the points discussed below, can be considered, for ease of understanding, as a "still" perspective representation of a fluttering flag (and in the case of a video signal could be changed for successive fields or frames so that the image is manipulated in such a manner that its plane is distorted to lie on the surface of a moving fluttering flag). Thus, a three-dimensional effect is achieved.
The address generator 14 is operative in this case to map the successive input samples into memory locations corresponding to the area 18. Thus, the first sample is not in this case stored in the memory location (0,1), but instead is stored in a location (xa,ya). Similarly, the next sample is not stored in the location (0,2), but is stored in a location (xb,yb); and so on. When the image is read out, the memory locations are read in the same order as in the case of FIG. 1, namely in the order (0,1) to (0,n), (1,1) to (1,n) . . . (m,1) to (m,n). Consequently, the output image has been manipulated in that an image which, in the absence of manipulation, would have conformed to the border of the memory 12 as represented in FIG. 2, will instead adopt the form represented by the area 18.
The output image has been subjected to manipulation of two types, namely (i) compression and (ii) rotation.
Considering first compression, in the example illustrated in FIG. 2 the image has been compressed (reduced in size) with respect to the original image in both the horizontal direction (along the lines (scanning lines) of the original or input image) and the vertical direction (transverse to the lines of the original or input image). Overall, the degree of compression in both directions is about 2:1. However, the degree of compression in either or both directions varies over the area 18. That is, it will in general be lesser over portions of the area intended to appear relatively near to the viewer and greater over portions of the area intended to appear further from the viewer. More generally, the degree or extent of compression (also referred to herein as the "scaling factor") is, at least in general, specific to small portions of the image. This can perhaps more readily be appreciated by an inspection of FIG. 3 of the accompanying drawings, which shows a case in which the input image is mapped on to an area 18' to give an effect equivalent to a perspective view of the input image plane. It will be seen that in this case the horizontal scaling factor (the degree of compression in the horizontal direction) increases in the downward direction.
With regard to rotation, it will be evident that, for example, a portion of the area indicated at 20 in FIG. 2 is subjected to little or no rotation with respect to the corresponding portion of the input picture, whereas a portion indicated at 22 has been rotated by about 45.degree..
As will now be described in detail, in the absence of corrective measures both compression and rotation of the picture can give rise to aliasing, which will degrade the quality of the output image.
Aliasing due to compression will be considered first. As is known to those skilled in the art, an image can be characterised by a two-dimensional parameter known as spatial frequency, which is proportional to the reciprocal of the angle subtended to the eye of the viewer by the visual spectral components of the image. The concept of spatial frequency can more readily be appreciated by considering an image in the form of a series of uniformly spaced straight lines. For a fixed position of the viewer with respect to such an image, the image has a single spatial frequency which is inversely proportional to the apparent spacing of the lines. (The spatial frequency is horizontal if the lines are vertical lines spaced horizontally, vertical if the lines are horizontal lines spaced vertically, and diagonal in other cases). Clearly, if the image is compressed, so that the lines appear to the viewer to become closer together whereby the angle they subtend to the eye of the viewer decreases, the spatial frequency increases.
The scaling theorem in Fourier analysis states that if an image signal is compressed in the spatial domain, that is if the spatial frequency of the image is increased, then the Fourier transform of the signal increases in the frequency domain (that is, the frequency (in Hz) of the signal increases); and vice versa.
It will be recalled that the image signal discussed above is a sampled signal. Nyquist's Rule concerning the sampling of signals states that, in order not to lose information contained in a signal, the signal must be sampled at a frequency (fs) that is equal to at least twice the bandwidth (fB) of the signal. Naturally, this criterion is complied with when the digital input signal is formed initially by sampling an analog signal. The frequency spectrum (Fourier transform) of the sampled signal in the frequency domain is shown by solid lines in FIG. 4 of the accompanying drawings, which is a graph of amplitude v. frequency (Hz). The frequency spectrum comprises a baseband component 24 (up to fB). Also, the baseband is reflected symmetrically around the sampling frequency fs and its harmonics 2fs, 3fs etc. to produce higher frequency components 26. Provided that Nyquist's Rule is complied with (so that fs/2 is greater than fB) and provided that the signal is band-limited (low-pass filtered) so as to have a cut-off frequency of about fs/2, the higher frequency components 26 will be suppressed.
As explained above, when the sampled signal is subjected to compression in the spatial domain, its Fourier transform exhibits expansion in the frequency domain. Thus, the bandwidths of the components 24, 26 in FIG. 4 increase. As shown by dotted lines in FIG. 4, this can result in aliasing of the signal in that the bandwidth fB of the signal can exceed the Nyquist limit (fs/2) so that part of at least the lowest one of the higher frequency components 26 extends down into and is mixed with the baseband so as to degrade the signal and therefore the image that it represents.
The phenomenon of aliasing due to rotation will now be described. As is known to those skilled in the art, the bandwidth of a system for handling the two-dimensional (vertical/horizontal) sampled image signal can be represented in the spatial domain by a two-dimensional frequency response as represented in FIG. 5 of the accompanying drawings. In FIG. 5, the horizontal axis represents a scale of horizontal spatial frequency in the positive and negative senses (H+ and H-) in units of cycles per picture width, the vertical axis represents a scale of vertical spatial frequency in the positive and negative senses (V+ and V-) in units of cycles per picture height, and the rectangle 28 represents the two-dimensional bandwidth of the system, the vertical and horizontal bandwidths being assumed to be approximately equal. It can be seen from FIG. 5 that diagonal frequencies (e.g. that shown at 30) of values higher than the vertical and horizontal bandwidths will fall within the two-dimensional bandwidth 28. If, for example, the vertical and horizontal bandwidths are equal, then diagonal frequencies of values up to .sqroot.2 times the horizontal/vertical bandwidth fall within the two-dimensional bandwidth 28. However, as will now be explained, this holds true only if the image is not rotated.
FIG. 6 of the accompanying drawings repeats the showing of FIG. 5 and shows also the frequency space 32 of an image which would fall just within the bandwidth 28 (in both dimensions) if the image had not been rotated, but which in fact has been rotated through 45.degree.. As will be seen, the corner regions (shown cross-hatched) of the frequency space 32 fall outside of the bandwidth 28 and therefore may exceed the Nyquist limit (fs/2) in the frequency domain, whereby they are reflected back into the bandwidth 28 (as shown by dotted lines) to mix with the baseband and cause aliasing in a generally similar manner to that explained above for the case of aliasing due to compression.
The extent of aliasing will depend upon the angle of rotation. If the horizontal and vertical bandwidths are the same, it will be appreciated that there is maximum likelihood of aliasing for angles of rotation of 45.degree., 135.degree., 225.degree. and 315.degree. and a minimum likelihood of aliasing for angles of rotation of 0.degree., 90.degree., 180.degree. and 270.degree..
Image signal processing apparatus designed to eliminate or reduce aliasing caused by the above-described phenomena is known. UK Patent Specification No GB-B-2 158 322 (Quantel Limited), and corresponding U.S. Pat. No. 4,665,433 (issued May 12, 1987 to Hinson et al), disclose such an apparatus which is designed so as to eliminate or reduce aliasing due to local compression. UK Patent Specification No GB-B-2 183 118 (Sony Corporation) discloses such an apparatus which is designed so as to eliminate or at least reduce aliasing due to local compression and/or rotation of the image. It does this by monitoring the addresses located to successive sets of at least three words or samples (spaced vertically and horizontally) corresponding to successive local areas of the image, computing from the addresses, for each such set of samples, horizontal and vertical local scaling factors representing the extent of compression and/or rotation of the corresponding local area, and varying the horizontal and vertical bandwidth of the signal in accordance with the local scaling factors in a sense to minimize aliasing that otherwise would be caused by compression and/or rotation.
The image signal processing apparatus of GB-B-2 183 118 is shown in FIG. 7 of the accompanying drawings. As can be seen from FIG. 7, the apparatus comprises, like the apparatus of FIG. 1, an input port or terminal 10, a memory 12, an address generator 14 and an output port or terminal 16, and is operative, like the apparatus of FIG. 1, to process a digital input image signal applied to the input port or terminal 10, by mapping it into the memory 12 in response to addresses produced by the address generator 14 in accordance with a mapping function, to produce a manipulated image output signal at the output port or terminal 16. Additionally, however, the apparatus of FIG. 7 includes a variable bandwidth digital filter 40 which is operative to effect two-dimensional filtering of the input signal before it is mapped into the memory 12, a local scaling factor computation means 42 connected to the address generator 14 to compute the local scaling factors from the addresses allocated to successive sets of samples, as just described, and bandwidth control means 44 responsive to the successive computed local scaling factors to vary the bandwidth of the filter 40, as just described, in a sense to minimize aliasing due to local compression and/or rotation of the image. The apparatus includes also a clock signal source (not shown) operative to produce clock pulses at the sample rate fs so as to cause the various illustrated components of the apparatus to perform their respective functions during respective successive clock periods T each equal to 1/fs.
In FIG. 7, as in FIG. 1, the input samples comprise multi-bit words. The bits of each word of the input signal generally will arrive in parallel (at the frequency or rate fs). Also, the bits of words produced internally of the apparatus generally are transferred between the various elements of the apparatus in parallel. Further, bits of each word (sample) of the output signal generally will be generated in parallel. (The same applies to FIGS. 15 to 19 described below). Accordingly, it will be appreciated that items in these figures that are shown or described as lines generally will in fact be in the form of busses or highways.
The principle of operation of the apparatus of FIG. 7 will now be described with reference to FIG. 8 of the accompanying drawings, which is a representation of the samples (words) of the input signal. The samples X01, X02, X03, X04 etc. represent the samples of the first line of the image, the samples X11, X12, X13, X14 etc. represent the samples of the second line of the image, and so on. As explained above, a respective address is generated for each sample by the address generator 14, the address representing the x and y coordinates of a location in the memory 12 in to which the sample is to be mapped. During each clock period, the local scaling factor computation means 42 is operative to compute local scaling factors based upon the addresses allocated to a set of at least three samples corresponding to a local image area. Provided that the set includes two samples that are relatively spaced horizontally and two samples that are relatively spaced vertically (which two groups of two samples may include one sample in common so that a set of only three samples suffices), the words of the set may have any desired predetermined relative disposition. One convenient form of set comprises two adjacent samples in one line and a sample appearing exactly one line after the earlier sample in the first-mentioned line. In this case, the sets of addresses monitored in successive clock periods would be those corresponding to the words X01, X02, X11; X02, X03, X12; X03, X04, X13 . . . X11, X12, X21; X12, X13, X22; and so on, as represented, for the first such set, by the dotted line boundary 46 in FIG. 8.
Consider what happens when, for example, the set of samples 46, namely the samples X01, X02, X11, is mapped to locations in the memory 12 represented in FIG. 8 as I1, I2 and I3, respectively. The locations I1, I2 and I3 are represented in FIG. 8 in their relative geometrical orientations in the output image and, as will be evident, the corresponding local image area has been subjected to rotation. It will be assumed also that the local image area has been subjected to compression in both the horizontal and vertical directions and that the extent or degree of compression (scaling factor) for each such direction differs from the other. Assume also that the x, y coordinates of the locations I1, I2 and I3, as indicated by their addresses, are (x1, y1), (x2, y2) and (x3, y3), respectively.
Simple trigonometry shows that the distance between the locations I1 and I2, which correspond to a pair of samples spaced horizontally by 1/fs (one pixel) in the input image, is given by: ##EQU1##
Accordingly, since the distance between the input samples X01, X02 corresponding to the locations I1, I2 is unity (one pixel), the degree of horizontal compression of the local area corresponding to the sample set 46 is given by: ##EQU2##
Similarly, it can be shown that the degree of vertical compression of the local area corresponding to the sample set 46 is given by: ##EQU3##
The bandwidth control means 44 is operative on the filter 40 during each clock period to reduce its horizontal and vertical bandwidths (as compared to the values of those bandwidths for the case when the image is not compressed) by the factors given in Equations (1) and (2), respectively, thereby preventing or at least reducing the generation of aliasing due to compression which otherwise would occur in the manner described above with reference to FIG. 4.
However, doing this alone would not prevent (or at least reduce) aliasing caused by rotation, which occurs for the reason explained above with reference to FIGS. 5 and 6. The prevention or reduction of aliasing due to rotation is accomplished as follows. The local scaling factor computation means 42 computes also the extent of rotation of the image. Specifically, it calculates the angle .theta.h of the line I1-I2 to the horizontal and the angle .theta.v of the line I1-I3 to the vertical, which angles indicate the amounts by which the local area has been rotated with respect to the horizontal and vertical, respectively, and which (in general) may not be the same. In practice, rather than computing .theta.h and .theta.v, it is more convenient to calculate their tangents, since tan .theta.h and tan .theta.v can be computed easily from the addresses of the points I1, I2 and I3 by the equations: ##EQU4##
Knowledge of the angles .theta.h and .theta.v (or their tangents) alone is not sufficient to deduce the amount of bandwidth reduction necessary to prevent aliasing due to rotation. As will be recalled from the explanation given above with reference of FIGS. 5 and 6, knowledge also is required of the likelihood of aliasing for the angle concerned. (For example, as indicated above, in the case of substantially equal horizontal and vertical bandwidths the likelihood of aliasing is maximum (and therefor maximum bandwidth reduction is required) if the angle is 45.degree., 135.degree., 225.degree. or 315.degree., whereas the likelihood of aliasing is minimum (and therefore minimum bandwidth reduction is required) if the angle is 0.degree., 90.degree., 180.degree. and 270.degree.). It is possible for the local scaling factor computation means 42 to calculate, from the computed values of tan .theta.h and tan .theta.v, corresponding values for F(.theta.h) and F(.theta.v), namely the reductions in the horizontal and vertical bandwidths, respectively, of the filter 40, needed to prevent aliasing due to rotation. Preferably, however, the computation means 42 contains look-up tables of F(.theta.h) and F(.theta.v) for various values of tan .theta.h and tan .theta.v and is operative to provide values of F(.theta.h) and F(.theta.v) appropriate to the calculated values of tan .theta.h and tan .theta.v by consulting the look-up tables.
Knowledge of both the compression bandwidth reduction factors as given by Equations (1) and (2) and of the rotation bandwidth reduction factors F(.theta.h) and F(.theta.v) enables the computation in the local scaling factor computation means 42 of horizontal and vertical scaling factors representing the extent by which the horizontal and vertical bandwidths of the filter 40 must be reduced (with respect to the values of those bandwidths when the image is neither compressed nor rotated) to prevent aliasing due to both compression and rotation. Specifically, the horizontal local scaling factor (horizontal bandwidth reduction factor) HLSF is given by ##EQU5## and the vertical local scaling factor (vertical bandwidth reduction factor) VLSF is given by ##EQU6##
Rotation of a local area of an image can be bodily in the sense that the axes of the area remain orthogonal after manipulation. (Thus, in that case, assuming no compression, the manipulated area would, though rotated, be of the same shape as before manipulation). Rotation can instead involve the axes of the area becoming other than orthogonal after manipulation. In other words, the manipulation can result in the area becoming sheared in the sense that an area in the shape of a rectangle would be transformed into a parallelogram.
Consider, for example, the manipulation of a square local area of an image shown in FIG. 9 of the accompanying drawings such that, as shown in FIG. 10, the vertical axis is rotated through 45.degree. and the horizontal axis is not rotated. The grid pattern on FIGS. 9 and 10 illustrates how the area becomes distorted. The area becomes sheared. The shearing of the area causes a horizontal component of the vertical frequency to be added to the horizontal frequency, whereas the vertical frequency remains the same. Thus, it becomes appropriate to consider the question of how much vertical filtering should be effected from the point of view of how the vertical frequency, which becomes diagonal as a result of shearing, affects the horizontal frequency. FIG. 11 of the accompanying drawings shows the area of FIG. 9 sheared in the same sense as in FIG. 10, but to a considerably greater extent. Comparing FIGS. 9 and 11, it will be seen that the spacing between the horizontal lines of the grid pattern, which represents the vertical frequency, is unchanged. But, the spacing between the vertical lines of the grid pattern, which represents the horizontal frequency, is greatly reduced. That is, the horizontal frequency produces a higher frequency in a diagonal direction. There is a need for greater filtering in the horizontal direction because the horizontal component will alias vertically.
GB-B-2 183 118 (cited above) deals with the possibility that manipulation may involve rotation of the axes of a local picture area by respective different angular extents by calculating respective different angles of a manipulated picture area to the horizontal and vertical, respectively, and adjusting local compression factors in accordance with functions of the calculated angles. However, it is believed that the approach adopted in GB-B-2 183 118 may not take full account of the problems resulting from shearing.